package com.sort.shell;

public class ShellSort {
    private int[] array;

    public ShellSort(int[] array) {
        this.array = array;
    }

    // 移位法
    public int[] sort_move() {
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) {
                int index = i - gap;
                int value = array[i];
                while (index >= 0 && value < array[index]) {
                    array[index + gap] = array[index];
                    index -= gap;
                }
                if (index + gap != i) {
                    array[index + gap] = value;
                }
            }
        }

        return this.array;
    }

    // 交换法，效率较低
    public int[] sort_exchange() {
        int tmp = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > array[j + gap]) {
                        tmp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = tmp;
                    }
                }
            }
        }

        return this.array;
    }
}
